/*!
 Temelia - Treap tree implementation source file.

 Copyright (C) 2008, 2009 Ceata (http://ceata.org/proiecte/temelia).

 @author Dascalu Laurentiu

 This program is free software; you can redistribute it and
 modify it under the terms of the GNU General Public License
 as published by the Free Software Foundation; either version 3
 of the License, or (at your option) any later version.

 This program is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 GNU General Public License for more details.

 You should have received a copy of the GNU General Public License
 along with this program; if not, write to the Free Software
 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
 */

#include "include/treap_tree.h"
#include "include/stack.h"
#include <stdlib.h>

/*
 * Treap, type of binary tree has this name because it respects conditions imposed
 * by binary search tree([1] and [2]) and heap([3]) :
 * 	1. if u is left descendant of v, key[u] < key[v]
 * 	2. if u is right descendant of v, key[u] > key[v]
 * 	3. if u is a child of v, priority[u] <= priority[v]
 */
struct _treap_node_t
{
	/*! user's key */
	void *key;

	/*! priority */
	unsigned int priority;
};

typedef struct _treap_node_t *treap_node;

#define GET_TREAP_MEMBER(x, member)   (((treap_node)(x))->member)
#define MAX_PRIORITY                  (10000)

extern stack_t iterating_handlers;
extern stack_t compare_stack;

/*!
 * Encapsulates user's key into a treap node.
 */
static treap_node_t _treap_node_new(void *key, unsigned int priority);

static void _treap_node_delete_node(treap_node_t);

static void _treap_internal_handling(void *x, void *context);

static void _treap_internal_printing_level(void *x, int level, void *context);

static int _treap_internal_compare(void *x, void *y, void *context);

treap_tree_t treap_tree_new(void *key)
{
	return _binary_tree_new(_treap_node_new(key, _rand() % MAX_PRIORITY + 1));
}

void treap_tree_delete_node(treap_tree_t treap)
{
	_ASSERT(treap, ==, NULL, NULL_POINTER,);

	_treap_node_delete_node(_binary_tree_get_key(treap));
	_delete(treap);
}

void treap_tree_delete(treap_tree_t treap)
{
	_ASSERT(treap, ==, NULL, NULL_POINTER,);

	treap_tree_delete(_binary_tree_get_left_child(treap));
	treap_tree_delete(_binary_tree_get_right_child(treap));
	treap_tree_delete_node(treap);
}

int treap_tree_compare_trees(treap_tree_t treap1, treap_tree_t treap2,
		int(*compare)(void *x, void *y, void *context), void *context)
{
	int result;

	stack_push(compare_stack, compare);

	result = _binary_tree_compare_trees(treap1, treap2,
			_treap_internal_compare, context);

	stack_pop(compare_stack);

	return result;
}

int treap_tree_is_empty(treap_tree_t treap)
{
	_ASSERT(treap, ==, NULL, NULL_POINTER, 1);

	return (_binary_tree_get_parent(treap) == NULL)
			&& (_binary_tree_get_left_child(treap) == NULL)
			&& (_binary_tree_get_right_child(treap) == NULL)
			&& (GET_TREAP_MEMBER(_binary_tree_get_key(treap), key) == NULL);
}

int treap_tree_is_leaf(treap_tree_t treap)
{
	return _binary_tree_leaf(treap);
}

int treap_tree_get_size(treap_tree_t treap)
{
	return _binary_tree_get_size(treap);
}

treap_tree_t treap_tree_get_root(treap_tree_t treap)
{
	return _binary_tree_get_root(treap);
}

void *treap_tree_get_key(treap_tree_t treap)
{
	treap_node_t node;

	_ASSERT(treap, ==, NULL, NULL_POINTER, NULL);

	node = _binary_tree_get_key(treap);

	return node->key;
}

unsigned int treap_tree_get_priority(treap_tree_t treap)
{
	treap_node_t node;

	_ASSERT(treap, ==, NULL, NULL_POINTER, 0);

	node = _binary_tree_get_key(treap);

	return node->priority;
}

treap_tree_t treap_tree_get_parent(treap_tree_t treap)
{
	return _binary_tree_get_parent(treap);
}

treap_tree_t treap_tree_get_left_child(treap_tree_t treap)
{
	return _binary_tree_get_left_child(treap);
}

treap_tree_t treap_tree_get_right_child(treap_tree_t treap)
{
	return _binary_tree_get_right_child(treap);
}

int treap_tree_get_height(treap_tree_t treap)
{
	return _binary_tree_get_height(treap);
}

int treap_tree_get_depth(treap_tree_t treap)
{
	return _binary_tree_get_depth(treap);
}

treap_tree_t treap_tree_search(treap_tree_t treap, void *key, int compare(
		void *x, void *y, void *context), void *context)
{

	treap_node search_node = _treap_node_new(key, -1);
	treap_tree_t result;

	stack_push(compare_stack, compare);

	result = _binary_search_tree_search(treap, search_node,
			_treap_internal_compare, context);
	_treap_node_delete_node(search_node);

	stack_pop(compare_stack);

	return result;
}

treap_tree_t treap_tree_insert(treap_tree_t *treap, void *key, int compare(
		void *x, void *y, void *context), void *context, int adjust_root)
{
	treap_tree_t add = NULL, parent = NULL, aux = NULL;
	treap_node_t add_node = NULL;
	_ASSERT(compare, ==, NULL, INVALID_INPUT, NULL);

	/*
	 * The algorithm is :
	 * Treap-Insert(k,p)
	 * 	if void *== null then void *<- new_node()
	 * 		void *-> [key, priority, lchild, rchild] <- [k, p, tnull, tnull]
	 * 	else if k < void *->key then Treap-Insert((k,p), void *->lchild)
	 * 			if void *->lchild->priority > void *->priority then Rotate-Right(void *)
	 * 	else if k > void *->key then Treap-Insert((k,p), void *->rchild)
	 * 			if void *->rchild->priority > void *->priority then Rotate-Left(void *)
	 * 	else
	 * 		key is already in the treap
	 */

	stack_push(compare_stack, compare);
	add_node = _treap_node_new(key, _rand() % MAX_PRIORITY + 1);
	aux = add = _binary_search_tree_insert(*treap, add_node,
			_treap_internal_compare, context);

	// key already exists - no adding in performed
	if (aux == NULL)
	{
		_treap_node_delete_node(add_node);
		return NULL;
	}

	while (add != *treap)
	{
		parent = _binary_tree_get_parent(add);

		if (_treap_internal_compare(_binary_tree_get_key(parent),
				_binary_tree_get_key(add), context) > 0
				&& GET_TREAP_MEMBER(_binary_tree_get_key(parent), priority)
						> GET_TREAP_MEMBER(_binary_tree_get_key(add), priority))
			_self_balanced_binary_search_tree_rotate_right(parent);

		if (_treap_internal_compare(_binary_tree_get_key(parent),
				_binary_tree_get_key(add), context) < 0
				&& GET_TREAP_MEMBER(_binary_tree_get_key(parent), priority)
						> GET_TREAP_MEMBER(_binary_tree_get_key(add), priority))
			_self_balanced_binary_search_tree_rotate_left(parent);

		add = parent;
	}

	while (adjust_root && _binary_tree_get_parent(*treap))
		(*treap) = _binary_tree_get_parent(*treap);

	stack_pop(compare_stack);
	return aux;
}

treap_tree_t treap_tree_remove(treap_tree_t *treap, void *key, int compare(
		void *x, void *y, void *context), void *context, int adjust_root)
{
	/*
	 * The algorithm is :
	 * Treap-Delete(k, void *)
	 * 	tnull->key <- k
	 * 	Rec-Treap-Delete(k, void *)
	 *
	 * Rec-Treap-Delete(k, void *)
	 * 	if k < void *->key then Rec-Treap-Delete(k, void *->lchild)
	 * 	else if k > void *->key then Rec-Treap-Delete(k, void *->rchild)
	 * 	else Root-Delete(void *)
	 *
	 * Root-Delete(void *)
	 * 	if is_leaf(void *) then void *<- tnull
	 * 	else if void *->lchild->priority > void *->rchild->priority
	 * 			then Rotate-Right(void *) and Root-Delete(void *->rchild)
	 * 	else Rotate-Left(void *) and Root-Delete(void *->lchild)
	 */
	treap_tree_t deleted, parent, aux;
	treap_node_t key_encapsulated;

	_ASSERT(treap, ==, NULL, NULL_POINTER, NULL);
	_ASSERT(*treap, ==, NULL, NULL_POINTER, NULL);
	_ASSERT(compare, ==, NULL, NULL_POINTER, NULL);

	stack_push(compare_stack, compare);

	// Remove the node as in a binary search tree and then start tree balancing.
	key_encapsulated = _treap_node_new(key, -1);
	deleted = _binary_search_tree_remove(treap, key_encapsulated,
			_treap_internal_compare, context, &aux);

	_treap_node_delete_node(key_encapsulated);

	_ASSERT(aux, ==, NULL, ELEMENT_NOT_FOUND, NULL);

	if (aux == *treap && _binary_tree_get_parent(*treap) == NULL
			&& _binary_tree_get_left_child(*treap) == NULL
			&& _binary_tree_get_right_child(*treap) == NULL)
	{
		treap_tree_delete_node(aux);
		*treap = NULL;
		return NULL;
	}

	treap_tree_delete_node(aux);

	_ASSERT(deleted, ==, NULL, ELEMENT_NOT_FOUND, NULL);

	parent = aux = deleted;

	while (parent && (parent = _binary_tree_get_parent(deleted)) != *treap)
	{
		if (_binary_tree_get_left_child(parent)
				&& _binary_tree_get_right_child(parent))
		{
			if (GET_TREAP_MEMBER(_binary_tree_get_key(_binary_tree_get_left_child(parent)), priority)
					> GET_TREAP_MEMBER(_binary_tree_get_key(_binary_tree_get_right_child(parent)), priority))
				_self_balanced_binary_search_tree_rotate_right(parent);
			else
				_self_balanced_binary_search_tree_rotate_left(parent);

			deleted = _binary_tree_get_parent(parent);
		}
		else
			deleted = parent;
	}

	while (adjust_root && _binary_tree_get_parent(*treap))
		(*treap) = _binary_tree_get_parent(*treap);

	stack_pop(compare_stack);

	return aux;
}

treap_tree_t treap_tree_get_min(treap_tree_t treap)
{
	return _binary_search_tree_get_min(treap);
}

treap_tree_t treap_tree_get_max(treap_tree_t treap)
{
	return _binary_search_tree_get_max(treap);
}

void treap_tree_preorder(treap_tree_t treap, void key_handler(void *x,
		void *context), void *context)
{
	stack_push(iterating_handlers, key_handler);
	_binary_tree_preorder(treap, _treap_internal_handling, context);
	stack_pop(iterating_handlers);
}

void treap_tree_inorder(treap_tree_t treap, void key_handler(void *x,
		void *context), void *context)
{
	stack_push(iterating_handlers, key_handler);
	_binary_tree_inorder(treap, _treap_internal_handling, context);
	stack_pop(iterating_handlers);
}

void treap_tree_reverse_inorder(treap_tree_t treap, void key_handler(void *x,
		void *context), void *context)
{
	stack_push(iterating_handlers, key_handler);
	_binary_tree_reverse_inorder(treap, _treap_internal_handling, context);
	stack_pop(iterating_handlers);
}

void treap_tree_postorder(treap_tree_t treap, void key_handler(void *x,
		void *context), void *context)
{
	stack_push(iterating_handlers, key_handler);
	_binary_tree_postorder(treap, _treap_internal_handling, context);
	stack_pop(iterating_handlers);
}

void treap_tree_level_order(treap_tree_t treap, void key_handler(void *x,
		void *context), void *context)
{
	stack_push(iterating_handlers, key_handler);
	_binary_tree_level_order(treap, _treap_internal_handling, context);
	stack_pop(iterating_handlers);
}

void treap_tree_show_indented(treap_tree_t treap, void key_handler(void *x,
		int level, void *context), void *context)
{
	stack_push(iterating_handlers, key_handler);
	_binary_tree_show_indented(treap, _treap_internal_printing_level, context,
			0);
	stack_pop(iterating_handlers);
}

static treap_node_t _treap_node_new(void *key, unsigned int priority)
{
	treap_node_t treap;

	treap = (struct _treap_node_t *) _new(sizeof(struct _treap_node_t));
	treap->key = key;
	treap->priority = priority;

	return treap;
}

static void _treap_node_delete_node(treap_node_t treap_node)
{
	_ASSERT(treap_node, ==, NULL, NULL_POINTER,);

	_delete(treap_node);
}

static void _treap_internal_handling(void *x, void *context)
{
	void (*user_handling_function)(void *, void *);

	user_handling_function = stack_top(iterating_handlers);

	_ASSERT(user_handling_function, ==, NULL, NULL_POINTER,);

	user_handling_function(GET_TREAP_MEMBER(x, key), context);
}

static void _treap_internal_printing_level(void *x, int level, void *context)
{
	void (*user_printing_function_level)(void *, int, void *);

	user_printing_function_level = stack_top(iterating_handlers);

	_ASSERT(user_printing_function_level, ==, NULL, NULL_POINTER,);

	user_printing_function_level(GET_TREAP_MEMBER(x, key), level, context);
}

static int _treap_internal_compare(void *x, void *y, void *context)
{
	/*
	 * This is the delegate function and can compare treap tree nodes.
	 *
	 * For comparing key from nodes, i save the user comparison function in a global pointers stack.
	 */
	int (*user_comparison_function)(void *, void *, void *);

	user_comparison_function = stack_top(compare_stack);

	_ASSERT(user_comparison_function, ==, NULL, NULL_POINTER, -1);

	return user_comparison_function(GET_TREAP_MEMBER(x, key),
			GET_TREAP_MEMBER(y, key), context);
}
